Question 1
Consider a system with 16MB of memory and fixed partitions, all of size 64KB, answer the following:
a. Identify the minimum number of bits needed in an entry in the process table to record the partition to which a process has been allocated.
Number of partitions = 256 = 2^8
Number of bits needed to store one of 256 partition numbers = 8
b. Identify the number of bits in the limit register.
Partition addresses = 0 to 65535
Number of bits in the limit register = 16
Question 2
Consider a memory with a contiguous allocation scheme consisting of 4 partitions of 600K, 400K, 500K, and 300K (in order) respectively.
Given a set of processes with 200K, 300K, 470K, and 500K (in order):
a. Using first fit, how would you allocate the memory to them?
b. Using best fit, how would you allocate the memory to them?
c. Using worst fit, how would you allocate the memory to them?
Question 3
Consider a logical address space of sixty-four pages of 1024 words each mapped onto a physical memory of 32 frames.
a. How many bits are there in the logical address?
Number of bits in the logical address = 16 (since 64 pages, each 1024 words, so log2(64) + log2(1024) = 6 + 10 = 16)
b. How many bits are there in the physical address?
Number of bits in the physical address = 15 (since 32 frames, each 1024 words, so log2(32) + log2(1024) = 5 + 10 = 15)
Question 4
a. Consider a single-level paging system with the page table stored in memory.
Assume the usage of Translation Look-aside Buffer (TLB) with 70 percentage hit ratio, and also assume that it takes 30 nanoseconds to search the TLB and 200 nanoseconds to access memory.
Identify the effective memory access time.
Effective access time (single level paging system)
= 0.70 × (230 nanoseconds) + 0.30 × (430 nanoseconds)
= 161 + 129 = 290 nanoseconds
b. Repeat the above calculations for a two level paging system.
Effective access time (two level paging table)
= 0.70 × (230 nanoseconds) + 0.30 × (630 nanoseconds)
= 161 + 189 = 350 nanoseconds
Question 5
On a simple paging system, Translation Lookaside Buffer (TLB) holds the most active page entries and the full page table is stored in the main memory.
If reference to TLB takes 10 ns, and memory reference takes 180ns, identify the hit ratio to achieve an effective access time of 200ns.
If h is the hit ratio and p is the probability of references found in TLB, then
190p + (1-p) 370 = 200
190p + 370 – 370p = 200
370 – 200 = 370p – 190p
180p = 170
p = 170 / 180 = 0.9444
Hit ratio = h = 94.44%
Question 6
Consider a computer system with a 32-bit logical address and 4-KB page size.
The system supports up to 512MB of physical memory. How many entries are there in each of the following?
a. A conventional single-level page table
Number of pages = 2^20. Number of entries in a conventional single-level page table = 2^20.
b. An inverted page table
Number of frames = 2^17. Number of entries in an inverted page table = 2^17.
Question 7
Identify the page numbers and offsets for the following address references (Given as decimal numbers).
Assume the page size is 1-KB.
a. 19366
Page 18, Offset 934
b. 30000
Page 29, Offset 304
c. 256
Page 0, Offset 256
Question 8
Consider the following segment table:
Segment Base Length
0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96
What are the physical addresses for the following logical addresses?
a. 0, 430
219 + 430 = 649
b. 1, 10
2300 + 10 = 2310
c. 2, 500
Illegal reference, trap to operating system
d. 3, 400
1327 + 400 = 1727
e. 4, 112
Illegal reference, trap to operating system
Question 9
Consider a system that uses a two-level page table with page size of 4KB and 32-bit logical addresses.
The first 8 bits of the address serve as the index into the first-level page table.
a. How many bits are needed to specify the second-level index?
32 - (12 + 8) = 12 bits
b. How many entries are in a level-one page table?
2^8 = 256 entries
c. How many entries are in a level-two page table?
2^12 = 4096 entries
d. How many pages are in the virtual address space?
2^20 (Each 2^8 level-one page table entry accesses a level-two page table with 2^12 entries,
2^8 × 2^12 = 2^20)